package leo.mystudy.leetcode;

import leo.mystudy.pojo.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author leo
 * @version 1.0.0
 * @description
 * @create 2022/3/12 18:00
 */
public class No107LevelOrderBottom {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        preOrder(root, 0, map);
        return map.entrySet().stream().sorted(((o1, o2) -> o2.getKey().compareTo(o1.getKey())))
                .map(Map.Entry::getValue).collect(Collectors.toList());
    }

    private void preOrder(TreeNode node, int depth, Map<Integer, List<Integer>> map) {
        if (node == null) {
            return;
        }
        map.computeIfAbsent(depth, t -> new ArrayList<>()).add(node.val);
        preOrder(node.left, depth + 1, map);
        preOrder(node.right, depth + 1, map);
    }
}
